The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(O(1), O(n^1)).

(0) Obligation:

Runtime Complexity TRS:
The TRS R consists of the following rules:

3(1(x1)) → 4(1(x1))
5(9(x1)) → 2(6(5(x1)))
3(5(x1)) → 8(9(7(x1)))
9(x1) → 3(2(3(x1)))
8(4(x1)) → 6(x1)
2(6(x1)) → 4(3(x1))
3(8(x1)) → 3(2(7(x1)))
9(x1) → 5(0(2(x1)))
8(8(4(x1))) → 1(9(x1))
7(1(x1)) → 6(9(x1))
3(9(x1)) → 9(3(x1))
7(5(x1)) → 1(0(x1))

Rewrite Strategy: INNERMOST

(1) CpxTrsMatchBoundsProof (EQUIVALENT transformation)

A linear upper bound on the runtime complexity of the TRS R could be shown with a Match Bound [MATCHBOUNDS1,MATCHBOUNDS2] of 2.
The certificate found is represented by the following graph.

Start state: 1434
Accept states: [1435, 1436, 1437, 1438, 1439, 1440]
Transitions:
1434→1435[3_1|0]
1434→1436[5_1|0]
1434→1437[9_1|0]
1434→1438[8_1|0, 6_1|1]
1434→1439[2_1|0]
1434→1440[7_1|0]
1434→1434[1_1|0, 4_1|0, 6_1|0, 0_1|0]
1434→1441[3_1|1]
1434→1443[2_1|1]
1434→1445[1_1|1]
1434→1446[9_1|1]
1434→1447[3_1|1]
1434→1448[3_1|2]
1434→1450[2_1|2]
1441→1442[2_1|1]
1442→1437[3_1|1]
1443→1444[0_1|1]
1444→1437[5_1|1]
1445→1435[4_1|1]
1445→1441[4_1|1]
1445→1447[4_1|1]
1445→1448[4_1|1]
1446→1440[6_1|1]
1447→1439[4_1|1]
1447→1443[4_1|1]
1447→1450[4_1|1]
1448→1449[2_1|2]
1449→1446[3_1|2]
1450→1451[0_1|2]
1451→1446[5_1|2]

(2) BOUNDS(O(1), O(n^1))